package com.lry.pda.topdown;


import java.util.*;

import static com.lry.pda.topdown.SymbolDefine.*;


public class ParseTableBuilder {

    private Map<Integer,Symbols> symbolMap = new LinkedHashMap<>();

    private boolean runFirstSet = true;
    private boolean runFollowSet = true;

    private int[][] parseTable;
    List<int[]> yy_pushtab = new ArrayList<>();

    public ParseTableBuilder() {
        initProductions();
        initYyPushTable();
        runSelectionSet();
        buildParseTable();
    }

    private void buildParseTable() {
        initializeParseTable();
        setParseTable();
        printParseTable();
    }

    private void setParseTable() {
        for (Symbols symbols : symbolMap.values()) {
            if(SymbolDefine.isSymbolTerminals(symbols.symbol)){
                continue;
            }
            for(int i=0;i<symbols.selectSet.size();i++){
                Set<Integer> select = symbols.selectSet.get(i);
                for (Integer col : select) {
                    parseTable[symbols.symbol - NO_TERMINAL_VALUE_BASE][col] = symbols.productNums.get(i);
                }
            }
        }
        //stmt遇到EOI选择表达式0
//        parseTable[0][0] = 0;
    }

    private void printParseTable() {
        for (int i = 0; i < SymbolDefine.NO_TERMINAL_MAX_RANGE; i++) {
            for (int j = 0; j < SymbolDefine.TERMINAL_MAX_RANGE; j++) {
                System.out.print(parseTable[i][j] + " ");
            }
            System.out.print("\n");
        }
    }

    private void initializeParseTable() {
        parseTable = new int[SymbolDefine.NO_TERMINAL_MAX_RANGE][SymbolDefine.TERMINAL_MAX_RANGE];
        for (int i = 0; i < SymbolDefine.NO_TERMINAL_MAX_RANGE; i++) {
            for (int j = 0; j < SymbolDefine.TERMINAL_MAX_RANGE; j++) {
                parseTable[i][j] = -1;
            }
        }
    }

    //非终结符遇到当前扫描的字符类型（lp,rp,num_or_id，plus,times等应该触发的操作），返回的int值是yy_pushtab的下标
    public int getWhatToDo(int topOfStackSymbol, int lookAheadSymbol) {
        return parseTable[topOfStackSymbol - NO_TERMINAL_VALUE_BASE][lookAheadSymbol];
    }


    public int[] getPushTabItems(int whatToDo) {
        return yy_pushtab.get(whatToDo);
    }

    private void initYyPushTable() {
        //stmt -> 空
        int[] yyp0 = null;
        yy_pushtab.add(yyp0);

        //stmt -> {0} expr {1} semi stmt
        int[] yyp1 = new int[]{SymbolDefine.STMT, SymbolDefine.SEMI, SymbolDefine.ACTION_1, SymbolDefine.EXPR, SymbolDefine.ACTION_0};
        yy_pushtab.add(yyp1);

        //expr -> term expr_prime
        int[] yyp2 = new int[]{SymbolDefine.EXPR_PRIME, SymbolDefine.TERM};
        yy_pushtab.add(yyp2);

        //expr_prime -> plus {0} term {2} expr_prime
        int[] yyp3 = new int[] {SymbolDefine.EXPR_PRIME, SymbolDefine.ACTION_2, SymbolDefine.TERM, SymbolDefine.ACTION_0,
                SymbolDefine.PLUS};
        yy_pushtab.add(yyp3);

        //expr_prim -> 空
        int[] yyp4 = null;
        yy_pushtab.add(yyp4);

        //term -> factor term_prime
        int[] yyp5 = new int[] {SymbolDefine.TERM_PRIME, SymbolDefine.FACTOR};
        yy_pushtab.add(yyp5);

        //term_prime -> times {0} factor {3} term_prime
        int[] yyp6 = new int[] {SymbolDefine.TERM_PRIME, SymbolDefine.ACTION_3, SymbolDefine.FACTOR, SymbolDefine.ACTION_0,
                SymbolDefine.TIMES};
        yy_pushtab.add(yyp6);

        //term_prime -> 空
        int[] yyp7 = null;
        yy_pushtab.add(yyp7);

        //factor -> num_or_id {4}
        int[] yyp8 = new int[]{SymbolDefine.ACTION_4, SymbolDefine.NUM_OR_ID};
        yy_pushtab.add(yyp8);

        //factor -> lp expr rp
        int[] yyp9 = new int[] {SymbolDefine.RP, SymbolDefine.EXPR, SymbolDefine.LP};
        yy_pushtab.add(yyp9);

    }

    private void initProductions() {

        ArrayList<int[]> productions = new ArrayList<>();
        productions.add(new int[]{SymbolDefine.EOI});
        productions.add(new int[]{SymbolDefine.EXPR, SymbolDefine.SEMI, SymbolDefine.STMT});
        Symbols stmt = new Symbols(SymbolDefine.STMT, false, productions,Arrays.asList(0,1));
        symbolMap.put(SymbolDefine.STMT, stmt);


        productions = new ArrayList<>();
        productions.add(new int[] {SymbolDefine.TERM, SymbolDefine.EXPR_PRIME});
        Symbols expr = new Symbols(SymbolDefine.EXPR, false, productions,Arrays.asList(2));
        symbolMap.put(SymbolDefine.EXPR, expr);

        productions = new ArrayList<>();
        productions.add(new int[] {SymbolDefine.PLUS, SymbolDefine.TERM, SymbolDefine.EXPR_PRIME});
        productions.add(new int[0]);
        Symbols expr_prime = new Symbols(SymbolDefine.EXPR_PRIME, true, productions,Arrays.asList(3,4));
        symbolMap.put(SymbolDefine.EXPR_PRIME, expr_prime);

        productions = new ArrayList<>();
        productions.add(new int[]{SymbolDefine.FACTOR, SymbolDefine.TERM_PRIME});
        Symbols term = new Symbols(SymbolDefine.TERM, false, productions,Arrays.asList(5));
        symbolMap.put(SymbolDefine.TERM, term);

        productions = new ArrayList<>();
        productions.add(new int[] {SymbolDefine.TIMES, SymbolDefine.FACTOR, SymbolDefine.TERM_PRIME});
        productions.add(new int[0]);
        Symbols term_prime = new Symbols(SymbolDefine.TERM_PRIME, true, productions,Arrays.asList(6,7));
        symbolMap.put(SymbolDefine.TERM_PRIME, term_prime);

        productions = new ArrayList<>();
        productions.add(new int[] {SymbolDefine.NUM_OR_ID});
        productions.add(new int[] {SymbolDefine.LP, SymbolDefine.EXPR, SymbolDefine.RP});
        Symbols factor = new Symbols(SymbolDefine.FACTOR, false, productions,Arrays.asList(8,9));
        symbolMap.put(SymbolDefine.FACTOR, factor);

        Symbols semi = new Symbols(SymbolDefine.SEMI, false, null,null);
        symbolMap.put(SymbolDefine.SEMI, semi);

        Symbols plus = new Symbols(SymbolDefine.PLUS, false, null,null);
        symbolMap.put(SymbolDefine.PLUS, plus);

        Symbols times = new Symbols(SymbolDefine.TIMES, false, null,null);
        symbolMap.put(SymbolDefine.TIMES, times);

        Symbols lp = new Symbols(SymbolDefine.LP, false, null,null);
        symbolMap.put(SymbolDefine.LP, lp);

        Symbols rp = new Symbols(SymbolDefine.RP, false, null,null);
        symbolMap.put(SymbolDefine.RP, rp);

        Symbols num_or_id = new Symbols(SymbolDefine.NUM_OR_ID, false, null,null);
        symbolMap.put(SymbolDefine.NUM_OR_ID, num_or_id);

        Symbols eoi = new Symbols(SymbolDefine.EOI, false, null,null);
        symbolMap.put(SymbolDefine.EOI, eoi);
    }

    public void runSelectionSet() {
        runFollowSets();

        for (Symbols symbols : symbolMap.values()) {
            addSymbolSelectionSet(symbols);
        }
    }

    /**
     *
     * 1. 计算first set和 follow set
     *
     * 2.对应非nullable的表达式 , s -> a b… 其中s是非终结符，
     * a 是一个或多个nullable的非终结符，b是终结符或是非终结符但不是nullable的，
     * b后面可以跟着一系列符号，假设其标号为N,那么该表达式的选择集就是FIRST(a) 和 FIRST(b)的并集。
     * 如果a不存在，也就是b的前面没有nullable的非终结符，那么SELECT(N) = FIRST(b).
     *
     *
     * 3.对应nullable的表达式: s -> a, s是非终结符，a是零个或多个nullable非终结符的集合，
     * a也可以是ε，假设该表达式标号为N,那么SELECT(N)就是 FIRST(a) 和 FOLLOW(s)的并集。
     * 由于a可以是0个非终结符，也就是s -> ε,从而s可以推导为空，如果s推导为空时，
     * 那么我们就需要看看当前输入字符是不是FOLLOW(s)，也就是跟在s推导后面的输入字符，
     * 如果是的话，我们才可以采用s->ε,去解析当前输入。
     * @param symbols
     */
    private void addSymbolSelectionSet(Symbols symbols) {
        if(SymbolDefine.isSymbolTerminals(symbols.symbol)){
            return;
        }
        boolean isNullableProduction = true;

        for (int[] production : symbols.productions) {
            Set<Integer> select = new HashSet<>();

            for(int v:production){
                Symbols next = symbolMap.get(v);
                select.addAll(next.firstSet);
                if(!next.nullable){
                    isNullableProduction = false;
                    break;
                }
            }

            if(isNullableProduction){
                select.addAll(symbols.followSet);
            }

            symbols.selectSet.add(select);
            isNullableProduction = true;
        }
    }



    public void runFollowSets() {
        runFirstSets();

        while(runFollowSet){
            runFollowSet = false;
            for (Symbols symbols : symbolMap.values()) {
                addSymbolFollowSet(symbols);
            }
        }
    }

    private void addSymbolFollowSet(Symbols symbols) {
        if(SymbolDefine.isSymbolTerminals(symbols.symbol)){
            return;
        }
        for (int[] production : symbols.productions) {
            if (production.length == 0) {
                continue;
            }
            //nullable的一定是非终结符
            //终结符一定是非nullable的

            //E -> T E'
            //规则1：对于 S -> A A1 A2....An B, A是非终结符，A1-An是nullable的，B是非nullable的，则Follow(A) = First(A1) + First(A2) + ... + First(An) + First(B)

            //遍历产生式每个终结符，非终结符
            for(int i=0;i<production.length;i++){
                Symbols cur = symbolMap.get(production[i]);
                if(SymbolDefine.isSymbolTerminals(cur.symbol)){
                    continue;
                }
                //对于产生式T E'来说，此时i指向T,j指向E'
                for(int j=i+1;j<production.length;j++){
                    Symbols next = symbolMap.get(production[j]);
                    addFollowSet(cur, next.firstSet);
                    if(!next.nullable){
                        break;
                    }
                }
            }

            //规则2：对于 S -> A A1 A2....An, A是非终结符，A1-An是nullable的，则Follow(A) ，Follow(A1)，Follow(A2)， ... ， Follow(An) 都包含 Follow(S)
            for(int i=production.length-1;i>=0;i--) {
                Symbols cur = symbolMap.get(production[i]);
                if(!SymbolDefine.isSymbolTerminals(cur.symbol)){
                    addFollowSet(cur,symbols.followSet);
                }
                if(!cur.nullable || SymbolDefine.isSymbolTerminals(cur.symbol)){
                    break;
                }
            }

        }
    }

    private void addFollowSet(Symbols symbols, Set<Integer> set){
        if(!symbols.followSet.containsAll(set)){
            runFollowSet = true;
        }
        symbols.followSet.addAll(set);
    }




    public void runFirstSets() {
        while(runFirstSet){
            runFirstSet = false;
            for (Symbols symbols : symbolMap.values()) {
                addSymbolFirstSet(symbols);
            }
        }
    }

    private void addSymbolFirstSet(Symbols symbols) {
        if(SymbolDefine.isSymbolTerminals(symbols.symbol)){
            return;
        }

        //遍历某个表达式的所有产生式，执行如下规则：
        //如果推导式右边第一个是终结符，那么firstSet把这个终结符加进来
        //规则1： s -> A a ，A是终结符，则A属于first（s）
        //规则2：s -> b a, s和b是非终结符，且b是非nullable的，则fist(s) = first(b)
        //规则3：s -> a1 a2 ...an b, a1~an是nullable的(nullable的肯定是非终结符)，b是非nullable的非终结符或者是一个终结符
        //那么first(s) = fisrt(a1) + first(a2) +...+first(an) + first(b);

        for (int[] production : symbols.productions) {
            if(production.length==0){
                continue;
            }
            //规则1
            if(SymbolDefine.isSymbolTerminals(production[0])){
                if(!symbols.firstSet.contains(production[0])){
                    runFirstSet = true;
                }
                symbols.firstSet.add(production[0]);
            }
            //规则2，3
            else{
                int pos = 0;
                Symbols cur = null;
                do{
                    cur = symbolMap.get(production[pos]);

                    if(!symbols.firstSet.containsAll(cur.firstSet)){
                        runFirstSet = true;
                    }
                    symbols.firstSet.addAll(cur.firstSet);

                    pos++;
                }while (pos<production.length && cur.nullable);
            }
        }
    }

}
